    /*    
		1.sharedspace.h	
		共享内存的结构,静态链表的方法。
		堆结构的操作方法，UI;
	*/
// the queue's max size;
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// the queue's max size;
#define MAXSTUDENTNUM 16
#define MAX_NAME_LENGTH 16

#define PERM S_IRUSR|S_IWUSR|IPC_CREAT

#define ERR_EXIT(m) \
    do { \
        perror(m); \
        exit(EXIT_FAILURE); \
    } while(0)

//学生信息结点
struct student {
	//data
	int id;
	char name[MAX_NAME_LENGTH];
	//删除标志,-1代表已经删除/元素不存在,0代表拥有元素
	int flag;
};

//静态链表结构,在其上建立一个堆结构
struct static_link_list {
	int capacity;
	//信息结构
	struct student students[MAXSTUDENTNUM + 1];
	//控制结构
	int cursors[MAXSTUDENTNUM + 1];
};

//共享内存空间,包括一个lock和一个共享内存区域M
struct shared_space {
	int lock;
	struct static_link_list L;
};

typedef struct student Student;
typedef struct shared_space SharedSpace;
typedef struct static_link_list StaticLinkList;

//本进程测试用,模拟共享内存
 SharedSpace* create_shared_space() {
 	SharedSpace* s = (SharedSpace*)malloc(sizeof(SharedSpace));
 	return s;
 }

 //交换学生结点
 void swap(Student* s1, Student* s2) {
	 Student tmp = *s1;
	 *s1 = *s2;
	 *s2 = tmp;
 }

//初始化静态链表
void initializeStaticLinkList(StaticLinkList* L) {
	L->capacity = MAXSTUDENTNUM;
	for (int i = 0; i < MAXSTUDENTNUM + 1; i++) {
		L->cursors[i] = i;
		L->students[i].flag = -1;
		L->students[i].id = 0;
		strcpy(L->students[i].name, "null");
	}
	//头结点存储堆结构的长度
	L->students[0].flag = 0;
}

//初始化共享内存空间
void initializeSharedSpace(SharedSpace* s) {
	s->lock = 0;
	initializeStaticLinkList(&s->L);
}


//小顶堆push操作
int push(StaticLinkList*L, Student s) {
	if (L->capacity == L->students[0].flag) {
		printf("push()\n");
		return -1;
	}
	else {
		int key = s.id;
		int lastElementIndex = ++L->students[0].flag;
		int i = lastElementIndex;
		for (; L->students[i / 2].id > key; i /= 2) {
			L->students[i] = L->students[i / 2];
		}
		L->students[i] = s;
		return 0;
	}
}

//过滤
void percolation(StaticLinkList* L,int index ,int last) {
	int parent = index;
	int childIndex;
	for (; parent * 2 <= last; parent = childIndex) {
		childIndex = 2 * parent;
		if (childIndex != last &&
			L->students[childIndex + 1].id < L->students[childIndex].id) {
			childIndex++;
		}
		if (L->students[parent].id > L->students[childIndex].id&&
			L->students[childIndex].flag != -1) {
			swap(&L->students[parent], &L->students[childIndex]);
		}
		else {
			break;
		}
	}
}

//重排
void heapSort(StaticLinkList*L) {
	int nums = L->students[0].flag;
	for (int i = 0; i < nums; i++) {
		swap(&L->students[nums-i], &L->students[1]);
		percolation(L, 1, nums - i - 1 );
	}
}

//先向上交换,然后再向下过滤
void adjust(StaticLinkList* L, int index, int last) {

	//检查父节点的值
	int i = index;
	for (; L->students[i / 2].id > L->students[i].id; i /= 2) {
		swap(&L->students[i / 2], &L->students[i]);
	}

	//向下过滤
	percolation(L, i, last);
}

//小顶堆delete操作
Student* deleteNode(StaticLinkList*L,int index) {
	int lastElementIndex = L->students[0].flag--;
	swap(&L->students[index], &L->students[lastElementIndex]);
	Student* deleteStudent = &L->students[lastElementIndex];
	L->students[lastElementIndex].flag = -1;
	adjust(L, index,lastElementIndex);

	return deleteStudent;
}



//静态链表查询操作 返回数组下标
int findIndex(StaticLinkList*L, int id) {
	for (int i = 0; i < L->capacity; i++) {
		if (L->students[i].id == id) {
			return i;
		}
	}
	return 0;
}

//静态链表查询操作
Student* find(StaticLinkList* L, int id) {
	for (int i = 0; i < L->capacity; i++) {
		if (L->students[i].id == id) {
			return &L->students[i];
		}
	}
	return &L->students[0];
}

//静态链表更新操作
int update(StaticLinkList*L, int id, Student newStd) {
	Student* s_ptr = find(L, id);
	if (s_ptr->id != 0) {
		*s_ptr = newStd;
		adjust(L, findIndex(L,newStd.id), L->students[0].flag);
		printf("[Update] 1 item.\n");
		return 0;
	}
	else {
		return -1;
	}
}

//根据用户输入查询相关信息
int findItem(SharedSpace* shared) {
	printf(">>>>>>Find[id] : ");
	int id;
	scanf("%d", &id);
	
	Student* s_ptr = find(&shared->L, id);
	if (s_ptr->id == 0) {
		return -1;
	}
	printf("[Find] id=%d:\n", id);
	printf("[Result] id=%d,name=%s\n", s_ptr->id, s_ptr->name);
	return 0;
}

//根据用户输入更新相关信息
int updateItem(SharedSpace* shared) {
	printf(">>>>>>Update[id] : ");
	int oldid;
	scanf("%d",&oldid);

	printf("[Find] id = %d,name = %s.\n", oldid, find(&shared->L, oldid)->name);

	char name_str[MAX_NAME_LENGTH];
	int sid;

	printf(">>>>>>Update[newId newName] : ");
	scanf("%d %s", &sid, name_str);
	Student std;
	std.id = sid;
	strcpy(std.name, name_str);

	while(shared->lock == 1){
		sleep(2);
	}

	shared->lock = 1;
	if (update(&shared->L, oldid, std) != -1) {
		printf("[Update] id=%d,name=%s\n", std.id, std.name);
	}
	shared->lock = 0;
	return 0;
}

//根据用户输入插入学生信息
int insert(SharedSpace* shared) {
	printf(">>>>>>Insert[id name] : ");
	char name_str[MAX_NAME_LENGTH];
	int sid;
	scanf("%d %s", &sid, name_str);
	Student std;
	std.id = sid;
	strcpy(std.name, name_str);
	while(shared->lock == 1){
		sleep(2);
	}

	shared->lock = 1;
	if (push(&shared->L, std) != -1) {
		printf("[Insert] id=%d,name=%s\n", std.id, std.name);
	}
	shared->lock = 0;
	return 0;
}

//删除指定结点
int deleteItem(SharedSpace*s) {
	printf(">>>>>>Delete[id] : ");
	int sid = 0;
	scanf("%d", &sid);
	int index = findIndex(&s->L, sid);
	if (index == 0) {
		printf("[Delete] fail.\n");
		return -1;
	}
	while(s->lock == 1){
		sleep(2);
	}
	//如果找到了,确定要删除就加锁进入共享内存空间进行操作.
	s->lock = 1;
	Student* std = deleteNode(&s->L,index);
	printf("[Delete] id=%d,name=%s\n", std->id, std->name);
	s->lock = 0;
	return 0;
}

//重建堆结构
void rebuild(SharedSpace*s) {
	while(s->lock == 1){
		sleep(2);
	}
	s->lock = 1;
	int last = s->L.students[0].flag;
	for (int i = last / 2; i > 0; i--) {
		percolation(&s->L, i, last);
	}
	s->lock = 0;
	printf("[Rebuild] Finish!\n");
}

//重排,将使堆失效
void resort(SharedSpace*s) {
	while(s->lock == 1){
		sleep(2);
	}
	s->lock = 1;
	heapSort(&s->L);
	printf("[Resort] Finish!\n");
	s->lock = 0;
}


//展示静态链表的结构
void showTable(SharedSpace* shared) {
	StaticLinkList*L = &shared->L;
	for (int i = 1; i < L->students[0].flag + 1; i++) {
		printf("[%d] id=%d;name=%s\n", i, L->students[i].id, L->students[i].name);
	}
}

//展示选项
void showOperation() {
	printf("------------------------------------\n");
	printf("i [ID NAME]插入.\n");
	printf("u [ID NAME] 更新学号为ID的学生,修改为NEWID NEWNAME.\n");
	printf("f [ID] 查找学号为ID的学生.\n");
	printf("d [ID] 删除指定学号的学生.\n");
	printf("c 重建堆结构.\n");
	printf("r 重排静态链表.\n");
	printf("p 查看链表.\n");
	printf("h 查看命令.\n");
	printf("------------------------------------\n");
}

//根据用户输入进行相关操作
void makeDecision(SharedSpace* shared, char choice) {
	if (choice == '\0' || choice == '\n') {
		return;
	}
	switch (choice)
	{
	case 'i':
		insert(shared);
		break;
	case 'd':
		deleteItem(shared);
		break;
	case 'p':
		showTable(shared);
		break;
	case 'f':
		findItem(shared);
		break;
	case 'u':
		updateItem(shared);
		break;
	case 'h':
		showOperation();
		break;
	case 'r':
		resort(shared);
		break;
	case 'c':
		rebuild(shared);
		break;
	default:
		printf("输入不合法.请重试\n");
		break;
	}
}